package yz.com.javautil.roadNetwork;

import java.util.*;

/**
 * 广度优先遍历（获取全部路径）
 * 参考资料：https://www.runoob.com/data-structures/graph-theory-path.html
 *
 * @author runoob
 */
public class AllShortestPath {
    /**
     * 图对象
     */
    private Graph graph;
    /**
     * 是否已访问
     */
    private boolean[] visited;
    /**
     * 记录路径 from[i] 表示查找的路径上i的上一个节点
     */
    private int[] from;
    /**
     * 记录路径中节点的次序 ord[i] 表示i节点在路径中的次序
     */
    private int[] ord;
    /**
     * 起始点
     */
    private int startPoint;
    /**
     * 记录全部可达路径
     */
    private List<Vector<Integer>> allPathList = new ArrayList<>();
    /**
     * 用于记录已循环路径
     */
    private DenseGraphImpl denseGraph;

    /**
     * 构造函数
     * 寻路算法（寻找图 graph 从 s 点到其他点的路径）
     *
     * @param graph      图对象
     * @param startPoint 起始点
     */
    public AllShortestPath(Graph graph, int startPoint, int endPoint) {
        // 算法数据初始化
        this.graph = graph;
        int pointNum = this.graph.getNodeNum();
        this.denseGraph = new DenseGraphImpl(pointNum, false);

        assert startPoint >= 0 && startPoint < pointNum;
        visited = new boolean[pointNum];
        from = new int[pointNum];
        ord = new int[pointNum];
        for (int i = 0; i < pointNum; i++) {
            visited[i] = false;
            from[i] = -1;
            ord[i] = -1;
        }
        // 无向图最短路径算法, 从 startPoint 开始广度优先遍历整张图
        this.startPoint = startPoint;
        LinkedList<Integer> pathPointList = new LinkedList<>();
        pathPointList.push(startPoint);
        visited[startPoint] = true;
        ord[startPoint] = 0;
        // 遍历每个顶点
        while (!pathPointList.isEmpty()) {
            int vertex = pathPointList.pop();
            if (vertex == endPoint) {
                Stack<Integer> stackPath = new Stack<>();
                // 通过from数组逆向查找到从s到w的路径, 存放到栈中
                int p = endPoint;
                while (p != -1) {
                    stackPath.push(p);
                    p = from[p];
                }
                // 从栈中依次取出元素, 获得顺序的从s到w的路径
                Vector<Integer> res = new Vector<>();
                while (!stackPath.empty()) {
                    res.add(stackPath.pop());
                }
                allPathList.add(res);
                // 清理状态
            }
            Vector<Integer> adjacentEdge = this.graph.getAdjacentEdge(vertex);
            for (int point : adjacentEdge) {
                if (!denseGraph.hasEdge(vertex, point)) {
                    denseGraph.addEdge(vertex, point);
                    pathPointList.push(point);
                    visited[point] = true;
                    from[point] = vertex;
                    ord[point] = ord[vertex] + 1;
                }
            }
        }
    }

    /**
     * 查询从s点到w点是否有路径
     *
     * @param w 目标
     * @return 是否有路径
     */
    private boolean hasPath(int w) {
        assert w >= 0 && w < graph.getNodeNum();
        return visited[w];
    }

    /**
     * 查询从s点到w点的路径, 存放在vec中
     *
     * @param w 目标
     * @return 路径
     */
    private Vector<Integer> path(int w) {
        assert hasPath(w);
        Stack<Integer> s = new Stack<>();
        // 通过from数组逆向查找到从s到w的路径, 存放到栈中
        int p = w;
        while (p != -1) {
            s.push(p);
            p = from[p];
        }
        // 从栈中依次取出元素, 获得顺序的从s到w的路径
        Vector<Integer> res = new Vector<>();
        while (!s.empty()) {
            res.add(s.pop());
        }
        return res;
    }


    /**
     * 查看从s点到w点的最短路径长度 若从s到w不可达，返回-1
     *
     * @param w 目标
     * @return 长度
     */
    public int length(int w) {
        assert w >= 0 && w < graph.getNodeNum();
        return ord[w];
    }

    /**
     * 打印s到w的路径
     *
     * @param w 目标点
     */
    public void showPath(int w) {
        assert hasPath(w);
        Vector<Integer> vec = path(w);
        for (int i = 0; i < vec.size(); i++) {
            System.out.print(vec.elementAt(i));
            if (i == vec.size() - 1) {
                System.out.println();
            } else {
                System.out.print(" -> ");
            }
        }
    }

    /**
     * 获取s到w的路径
     *
     * @param w 目标点
     */
    public Vector<Integer> getPath(int w) {
        assert hasPath(w);
        return path(w);
    }

    /**
     * 返回从s点到w点的路径
     */
    public List<Vector<Integer>> getAllPath() {
        return allPathList;
    }
}
